"""
归并排序
"""

l = [1, 3, 2, 5, 2, 9]


def merage(left, right):
    res = []
    while left and right:
        if left[0] <= right[0]:
            res.append(left[0])
            del left[0]
        else:
            res.append(right[0])
            del right[0]
    res.extend(left)
    res.extend(right)
    return res


def msort(data):
    if len(data) == 1:
        return data

    idx = int(len(data)/2)
    left = msort(data[:idx])
    right = msort(data[idx:])
    return merage(left, right)

print(msort(l))
